package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1017 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * 我承认有点蒙蔽
     * 其实本题想让我们得到的解题结果只包含0或者1，但是我们数学运算出来的结果却是0或-1；所以我们对结果进行修正
        比如数学运算 (-3)/(-2)等于1余-1，
        但是题目想让我们得到的结果是(-3)/(-2)等于2余1;我们看到把余数修正为1，需要我们把商加1;
        现在我们把描述一般化：
        把算式写成a-(-2)*b=c，其实a是被除数，b是商，c是余数
        等式两边同时减去(-2),得到a-(-2)b-(-2)=c-(-2)
        进行化简：a-(-2)(b+1)=c+2;
        此时 a是被除数，b+1是商，c+2是余数。
        所以当余数是-1时候，如果我们想把余数变为1，也就是变成了c+2；我们正确的商应该是b+1；原来的商加1
     * @return:
     */
    public class Solution {
        public String baseNeg2(int N) {
            StringBuilder res = new StringBuilder(40);
            while (N != 0) {
                int mod = N % (-2);
                N /= -2;
                if (mod == -1) {
                    res.append(1);
                    N++;//修正N
                } else {
                    res.append(mod);
                }
            }
            return res.length() == 0 ? "0" : res.reverse().toString();
        }
    }

    class Solution_Slow_Thinking {
        public String baseNeg2(int n) {
            String ori = Integer.toBinaryString(n);
            StringBuilder ans = new StringBuilder();
            int step1 = 0, step2 = 0, i = ori.length() - 1;
            boolean curEven = true;
            while (step1 != 0 || step2 != 0 || i >= 0) {
                int cur = step1 + (i >= 0 ? ori.charAt(i--) - '0' : 0);
                if (curEven) {
                    // 当前偶数位好办
                    ans.insert(0, cur % 2);
                    step1 = (cur / 2 + step2) % 2;
                    step2 = (cur / 2 + step2) / 2;
                } else {
                    ans.insert(0, cur % 2);
                    if (cur == 0) {
                        step1 = step2;
                        step2 = 0;
                    } else if (cur == 1) {
                        step1 = step2 + 1;
                        step2 = 0;
                    } else if (cur == 2) {
                        step1 = step2 + 1;
                        step2 = 1;
                    } else {
                        System.out.println("shit");
                    }
                }
                curEven = !curEven;
            }

            System.out.println(n + " -> " + check(ans));
            return ans.toString();
        }

        public int check(StringBuilder ans) {
            int checkSum = 0;
            for (int i = 0; i < ans.length(); i++) {
                checkSum += (ans.charAt(i) - '0') * Math.pow(-2, ans.length() - 1 - i);
            }

            return checkSum;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.baseNeg2(2));
//        System.out.println(solution.baseNeg2(3));
        System.out.println(solution.baseNeg2(14));
//        for (int i = 2; i <= 15; i++) {
//            System.out.println(solution.baseNeg2(i));
//        }
    }

    public static void main(String[] args) throws Exception {
        LC1017 an = new LC1017();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
